The growth of the Internet has increased the burden of transferring data from one destination to another. As a result, various protocols have been developed to ease this burden, trying to keep pace with the increasing Internet use. Unfortunately, not all of these protocols have been successful.
In the beginning, the Exterior Gateway Protocol (EGP) was created to exchange routing information between two neighboring gateway hosts. It was commonly used between hosts on the Internet to exchange routing table information. However, EGP became less capable as the Internet structure grew and became too unmanageable. EGP could not handle the increased size of the Internet nor could it deal well with having multiple connections to unrelated routing domains.
With the limitations of EGP, the Border Gateway Protocol (BGP) appeared primarily designed to handle arbitrarily connected networks. This is the structure that remains today. There are hundreds of networks operating in the Internet. These networks are connected in an arbitrary fashion to other networks. So, in order to have some routing rules, BGP operates to view the various networks operating in the Internet as autonomous systems (ASs).
An AS may be defined as a network operating in the Internet as an independent entity. An AS may be a corporate network, university campus network, or a series of smaller networks connected together. For example, a corporation may have several locations linking all of its locations together in a single network. This single network may be viewed as an AS. Likewise, the corporation may have several as depending on the structure it has implemented.
Each AS has a globally unique autonomous system number (AS identifier) so that an entity can be located in the Internet. Each AS can talk to another AS using the AS identifier. An AS may be connected to another AS either through a service provider, connection point, or direct connection. These connections establish how data may route from one AS to another.
Of the various types of AS, three are commonly encountered: a multihomed AS, a transit AS, and a stub AS. A multihomed AS is one that has multiple connections to other ASs. A multihomed AS may be found in entities such as large corporations that need connections to other networks. A transit AS is one that has multiple connections to other as and also allows data to transfer through it enroute to another destination. A stub AS is one that has one connection to another AS.
BGP runs in two modes: Exterior (or External) Border Gateway Protocol (EBGP or eBGP) and Interior (or Internal) Border Gateway Protocol (IBGP or iBGP). EBGP operates between two different as while IBGP operates within the same AS.
During the advancement of the Internet, other protocols have been implemented to improve BGP. For example, Secure BGP (S-BGP) was created to address security issues, such as authenticity of routing, around BGP. Secure Origin BGP (soBGP) was created to improve S-BGP by allowing service providers to authenticate routes and implement a more flexible routing policy. External and Internal Border Gateway Protocol (eiBGP) was created to work with the Multiprotocol Label Switching (MPLS) Virtual Private Networks (VPNs). EiBGP allows one to configure multipath load balancing with both EBGP and IBGP paths in BGP networks.
Although not explicitly discussed here, a foundation of the protocols is a use of routers to communicate with each other to transfer data. BGP and its variations use routers to route data from one AS to another. The routers are associated with an AS or service provider, and operate with routing policies to transfer data from a source to a destination. Several types of routers exist including provider edge routers (PE-routers) which function at the boundaries of a backbone service provider, and consumer edge routers (CE-routers) that function at the boundaries of an AS. The backbone service provider and AS may have other internal routers, but it is the PE-routers and CE-routers that communicate together at the boundaries to transfer data from one AS to another AS.
When bi-directional load balanced communication is required between two multihomed ASs, there is a desire to implement eiBGP multipath on all the PE-routers. When this happens, traffic that leaves a PE-router destined for a set of PE-routers connected to an AS will be load balanced between the set of PE-routers. Without eiBGP multipath implemented, some PE-routers may become under-utilized. The goal is to be able to balance traffic across PE-routers. In doing so, a problem may occur in causing routing loops. A routing loop may occur when data traffic is sent back and forth between PE-routers that are connected to the same AS. A cause of the routing loop is attributed to a change in the routing policy whereby a critical route selection rule is negated in the PE-routers (i.e. “that eBGP learned routes must be preferred over iBGP learned routes”) for the purposes of load balancing. Without this rule, eBGP routes and iBGP routes are made equal in the route selection process. Therefore, when a PE-router selects a route, it selects the route path with the closest distance or least cost. In most cases, this will be an iBGP route since the PE-routers are closer together in most cases or are connected to the same AS.
A solution is needed that would allow eiBGP multipath to be implemented on PE-routers but prohibit routing loops from occurring. The present invention implements this solution.